{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #分割回文串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: partition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分割回文串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个字符串 <code>s</code> ，请将 <code>s</code> 分割成一些子串，使每个子串都是 <strong>回文串</strong> ，返回 s 所有可能的分割方案。</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" /><strong>回文串</strong>&nbsp;是正着读和反着读都一样的字符串。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s =<strong> </strong>&quot;google&quot;\n",
    "<strong>输出：</strong>[[&quot;g&quot;,&quot;o&quot;,&quot;o&quot;,&quot;g&quot;,&quot;l&quot;,&quot;e&quot;],[&quot;g&quot;,&quot;oo&quot;,&quot;g&quot;,&quot;l&quot;,&quot;e&quot;],[&quot;goog&quot;,&quot;l&quot;,&quot;e&quot;]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = &quot;aab&quot;\n",
    "<strong>输出：</strong>[[&quot;a&quot;,&quot;a&quot;,&quot;b&quot;],[&quot;aa&quot;,&quot;b&quot;]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = &quot;a&quot;\n",
    "<strong>输出：</strong>[[&quot;a&quot;]]</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>提示：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 16</code></li>\n",
    "\t<li><code>s </code>仅由小写英文字母组成</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 131&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/palindrome-partitioning/\">https://leetcode-cn.com/problems/palindrome-partitioning/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [M99OJA](https://leetcode.cn/problems/M99OJA/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [M99OJA](https://leetcode.cn/problems/M99OJA/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"google\"', '\"aab\"', '\"a\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        def is_re(word):\n",
    "            word_len = len(word)\n",
    "            if word ==1:\n",
    "                return True\n",
    "            left = 0\n",
    "            right = word_len-1\n",
    "            while left<=right:\n",
    "                if word[left] != word[right]:\n",
    "                    return False\n",
    "                left+=1\n",
    "                right-=1\n",
    "            return True\n",
    "         \n",
    "        s_len = len(s)\n",
    "\n",
    "        s_list = [[s[i]] for i in range(s_len)]\n",
    "        for i in range(s_len-1,-1,-1):\n",
    "            for j in range(i-1,  -1,-1):\n",
    "                w = s[j:i+1]\n",
    "                if is_re(w):\n",
    "                    s_list[i].append(w)\n",
    "        # print(s_list)\n",
    "        def dfs(i):\n",
    "            if i<0:\n",
    "                return \n",
    "            cur = []\n",
    "            for w in s_list[i]:\n",
    "                word = dfs(i-len(w))\n",
    "                if word:\n",
    "                    for v in word:\n",
    "                        v.append(w)\n",
    "                        cur.append(v)\n",
    "                else:\n",
    "                    cur.append([w])\n",
    "            return cur\n",
    "        return dfs(s_len-1)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        self.split = []\n",
    "\n",
    "\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        if not s:\n",
    "            return []\n",
    "        self.backTracking(s, 0)\n",
    "        return self.res\n",
    "    \n",
    "    def backTracking(self, s, startIndex):\n",
    "        if startIndex == len(s):\n",
    "            self.res.append(self.split[:])\n",
    "            #print(\"add\")\n",
    "            return \n",
    "        for i in range(startIndex, len(s)):\n",
    "            part = s[startIndex:i+1]\n",
    "            if self.isPalindrome(part):\n",
    "                self.split.append(part)\n",
    "                self.backTracking(s, i + 1)\n",
    "                self.split.pop()\n",
    "        \n",
    "    def isPalindrome(self, part):\n",
    "        if len(part) == 1:\n",
    "            return True\n",
    "        l, r = 0, len(part) - 1\n",
    "        while l < r:\n",
    "            if part[l] != part[r]:\n",
    "                return False\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        #print(\"succeed\")\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "\n",
    "        def validate(s):\n",
    "            l, r = 0, len(s)-1\n",
    "            while l < r:\n",
    "                if s[l] != s[r]: return False\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            return True\n",
    "\n",
    "        def recur(s, start, split, res):\n",
    "            if start == len(s):\n",
    "                res.append(copy.deepcopy(split))\n",
    "            \n",
    "            for end in range(start, len(s)):\n",
    "                if not validate(s[start:end+1]):\n",
    "                    continue\n",
    "                split.append(s[start:end+1])\n",
    "                recur(s, end+1, split, res)\n",
    "                split.pop()\n",
    "        \n",
    "        res = []\n",
    "        recur(s, 0, [], res)\n",
    "        return res\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        n = len(s)\n",
    "\n",
    "        # 先找超过2个字符的长回文串\n",
    "        tmp = []  # (start, end)  # 索引start ~ end 是回文\n",
    "        \n",
    "        for i in range(n - 1):\n",
    "            # 找偶数回文串的中心, 中间两个字符肯定是一样的\n",
    "            if s[i] == s[i + 1]:\n",
    "                start = i\n",
    "                end = i + 1\n",
    "                while start > 0 and end < n - 1 and s[start - 1] == s[end + 1]:\n",
    "                    start = start - 1\n",
    "                    end = end + 1\n",
    "                tmp.append((start, end))\n",
    "\n",
    "            # 找奇数回文串的中心, aba形式\n",
    "            if i == n - 2:\n",
    "                continue\n",
    "            if s[i] == s[i + 2]:\n",
    "                start = i\n",
    "                end = i + 2\n",
    "                while start > 0 and end < n - 1 and s[start - 1] == s[end + 1]:\n",
    "                    start = start - 1\n",
    "                    end = end + 1\n",
    "                tmp.append((start, end))\n",
    "\n",
    "        @lru_cache\n",
    "        def get(index):\n",
    "            # 从 index 索引出发, 可以获取到哪些回文子串\n",
    "            rs = [(s[index], index + 1)]\n",
    "            for start, end in tmp:\n",
    "                if index >= start and index <= end and start + end - index > index:\n",
    "                    rs.append((s[index:start + end - index + 1], start + end - index + 1))\n",
    "            return rs\n",
    "\n",
    "\n",
    "        d = deque([([], 0)])  # (当前分割的子串列表, 下次分割位置)\n",
    "        result = []\n",
    "        while d:\n",
    "            lst, index = d.popleft()\n",
    "            if index == n:\n",
    "                result.append(lst)\n",
    "                continue\n",
    "            rs = get(index)\n",
    "            for i in range(1, len(rs)):\n",
    "                lstCopy = lst.copy()\n",
    "                lstCopy.append(rs[i][0])\n",
    "                d.append((lstCopy, rs[i][1]))\n",
    "            lst.append(rs[0][0])\n",
    "            d.append((lst, rs[0][1]))\n",
    "        return result\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        n = len(s)\n",
    "\n",
    "        # 先找超过2个字符的长回文串\n",
    "        tmp = []  # (start, end)  # 索引start ~ end 是回文\n",
    "        \n",
    "        for i in range(n - 1):\n",
    "            # 找偶数回文串的中心, 中间两个字符肯定是一样的\n",
    "            if s[i] == s[i + 1]:\n",
    "                start = i\n",
    "                end = i + 1\n",
    "                while start > 0 and end < n - 1 and s[start - 1] == s[end + 1]:\n",
    "                    start = start - 1\n",
    "                    end = end + 1\n",
    "                tmp.append((start, end))\n",
    "\n",
    "            # 找奇数回文串的中心, aba形式\n",
    "            if i == n - 2:\n",
    "                continue\n",
    "            if s[i] == s[i + 2]:\n",
    "                start = i\n",
    "                end = i + 2\n",
    "                while start > 0 and end < n - 1 and s[start - 1] == s[end + 1]:\n",
    "                    start = start - 1\n",
    "                    end = end + 1\n",
    "                tmp.append((start, end))\n",
    "\n",
    "        @lru_cache\n",
    "        def get(index):\n",
    "            # 从 index 索引出发, 可以获取到哪些回文子串\n",
    "            rs = [(s[index], index + 1)]\n",
    "            for start, end in tmp:\n",
    "                if index >= start and index <= end and start + end - index > index:\n",
    "                    rs.append((s[index:start + end - index + 1], start + end - index + 1))\n",
    "            return rs\n",
    "\n",
    "\n",
    "        d = deque([([], 0)])  # (当前分割的子串列表, 下次分割位置)\n",
    "        result = []\n",
    "        while d:\n",
    "            lst, index = d.popleft()\n",
    "            if index == n:\n",
    "                result.append(lst)\n",
    "                continue\n",
    "            rs = get(index)\n",
    "            for i in range(1, len(rs)):\n",
    "                lstCopy = lst.copy()\n",
    "                lstCopy.append(rs[i][0])\n",
    "                d.append((lstCopy, rs[i][1]))\n",
    "            lst.append(rs[0][0])\n",
    "            d.append((lst, rs[0][1]))\n",
    "        return result\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:####dp解法\n",
    "        result=[[s[0]]]\n",
    "        for i in range(1,len(s)):\n",
    "            for j in range(len(result)):\n",
    "                if result[j][-1]==s[i]:                   ### abbc b 当前字母是 b 可以新加abbc bb          \n",
    "                    result.append(result[j][:-1]+[s[i]+s[i]])\n",
    "                if len(result[j])>1 and result[j][-2]==s[i]:  ## a b cc 当前字母是 b 可以新加入 a bccb  \n",
    "                    result.append(result[j][:-2]+[s[i]+result[j][-1]+s[i]])\n",
    "                result[j].append(s[i])  ####单独加入  不支持合并 如 a bb 当前是d  只有单独直接加入      \n",
    "        result.sort()\n",
    "        return result\n",
    "    ########卡在 ‘fff’了与题目答案顺序不一样。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        q=[[s[0]]]\n",
    "        for i in range(1,len(s)):\n",
    "            for j in range(len(q)):\n",
    "                # q.append(q[j]+[s[i]])\n",
    "                if len(q[j])>=2 and s[i] == q[j][-2]:\n",
    "                    q.append(q[j][:-2] + [q[j][-2]+q[j][-1]+s[i]])\n",
    "                if s[i] == q[j][-1]:\n",
    "                    q.append(q[j][:-1] + [q[j][-1]+s[i]])\n",
    "                q[j].append(s[i])\n",
    "            # q = q[q_len:]\n",
    "        q.sort()\n",
    "        return q\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        dp = [[i >= j for j in range(len(s))] for i in range(len(s))]\n",
    "        # return dp\n",
    "        for i in range(len(s) - 1,-1,-1):\n",
    "            for j in range(i + 1, len(s)):\n",
    "                if dp[i + 1][j - 1] and s[i] == s[j]:\n",
    "                    dp[i][j] = True\n",
    "                    # return 5\n",
    "                else:\n",
    "                    dp[i][j] = False\n",
    "        # return dp\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        ans = []\n",
    "        def dfs(i, road):\n",
    "            if i == len(s):\n",
    "                ans.append(tuple(road))\n",
    "                return\n",
    "            for j in range(i, len(s)):\n",
    "                if dp[i][j]:\n",
    "                    road.append(s[i:j + 1])\n",
    "                    dfs(j + 1, road)\n",
    "                    road.pop(-1)\n",
    "            return\n",
    "            \n",
    "\n",
    "\n",
    "        dfs(0, [])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        if len(s)==0: return [[]]\n",
    "        if len(s)==1: return [[s]]\n",
    "        if len(s)==2: \n",
    "            if s[0]==s[1]: return [[s[0],s[1]],[s]]\n",
    "            else: return [[s[0],s[1]]]\n",
    "        rlist=[]\n",
    "        for i in range(len(s)):\n",
    "            a=s[:i+1]\n",
    "            if a!=a[::-1]: continue\n",
    "            r=self.partition(s[i+1:])\n",
    "            for j in range(len(r)):\n",
    "                rlist.append([a]+r[j])\n",
    "        return rlist\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        def is_re(word):\n",
    "            word_len = len(word)\n",
    "            if word ==1:\n",
    "                return True\n",
    "            left = 0\n",
    "            right = word_len-1\n",
    "            while left<=right:\n",
    "                if word[left] != word[right]:\n",
    "                    return False\n",
    "                left+=1\n",
    "                right-=1\n",
    "            return True\n",
    "         \n",
    "        s_len = len(s)\n",
    "\n",
    "        s_list = [[s[i]] for i in range(s_len)]\n",
    "        for i in range(s_len):\n",
    "            for j in range(i+2, s_len+1):\n",
    "                w = s[i:j]\n",
    "                if is_re(w):\n",
    "                    s_list[i].append(w)\n",
    "        # print(s_list)\n",
    "        def dfs(i):\n",
    "            if i>=s_len:\n",
    "                return []\n",
    "            cur = []\n",
    "            for w in s_list[i]:\n",
    "                word = dfs(i+len(w))\n",
    "                if word:\n",
    "                    for v in word:\n",
    "                        cur.append([w]+v)\n",
    "                else:\n",
    "                    cur.append([w])\n",
    "            return cur\n",
    "        return dfs(0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        def is_re(word):\n",
    "            word_len = len(word)\n",
    "            if word ==1:\n",
    "                return True\n",
    "            left = 0\n",
    "            right = word_len-1\n",
    "            while left<=right:\n",
    "                if word[left] != word[right]:\n",
    "                    return False\n",
    "                left+=1\n",
    "                right-=1\n",
    "            return True\n",
    "         \n",
    "        s_len = len(s)\n",
    "\n",
    "        s_list = [[s[i]] for i in range(s_len)]\n",
    "        for i in range(s_len):\n",
    "            for j in range(i+2, s_len+1):\n",
    "                w = s[i:j]\n",
    "                if is_re(w):\n",
    "                    s_list[i].append(w)\n",
    "        print(s_list)\n",
    "        def dfs(i):\n",
    "            if i>=s_len:\n",
    "                return []\n",
    "            cur = []\n",
    "            for w in s_list[i]:\n",
    "                word = dfs(i+len(w))\n",
    "                if word:\n",
    "                    for v in word:\n",
    "                        cur.append([w]+v)\n",
    "                else:\n",
    "                    cur.append([w])\n",
    "            return cur\n",
    "        return dfs(0)\n",
    "            \n",
    "                    \n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        ret = []\n",
    "        self.dfs(s, [], ret)\n",
    "        return ret\n",
    "    def dfs(self, s, path, ret):\n",
    "        if not s:\n",
    "            ret.append(path[:])\n",
    "        for i in range(len(s)):\n",
    "            if self.isPalindrome(s[:i+1]):\n",
    "                path.append(s[:i+1])\n",
    "                self.dfs(s[i+1:], path, ret)\n",
    "                path.pop()\n",
    "    \n",
    "    def isPalindrome(self, s):\n",
    "        return s == s[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        res = []\n",
    "        ans = []\n",
    "\n",
    "        # def isPalindrome(i: int, j: int) -> int:\n",
    "        #     if i >= j:\n",
    "        #         return 1\n",
    "        #     return isPalindrome(i + 1, j - 1) if s[i] == s[j] else -1\n",
    "\n",
    "        # def backtracking(s, start_index):\n",
    "        #     if start_index == len(s):\n",
    "        #         res.append(ans[:])\n",
    "        #         return # 忘了return 服啦\n",
    "            \n",
    "        #     for i in range(start_index, len(s)):\n",
    "        #         if isPalindrome(start_index, i) == 1:\n",
    "        #             ans.append(s[start_index: i+1])\n",
    "        #             backtracking(s, i+1) # 不能重复切割\n",
    "        #             ans.pop()\n",
    "        #         else: # 不是回文字串，不能往下递归遍历，而是接着往右执行for循环\n",
    "        #             continue\n",
    "        \n",
    "        # backtracking(s, 0)\n",
    "        # return res\n",
    "\n",
    "\n",
    "        def isPalindrome(i: int, j: int) -> int:\n",
    "            if i >= j:\n",
    "                return 1\n",
    "            return isPalindrome(i + 1, j - 1) if s[i] == s[j] else -1\n",
    "\n",
    "        def backtracking(s, res, ans, start_index):\n",
    "            if start_index == len(s):\n",
    "                res.append(ans[:])\n",
    "                return # 忘了return 服啦\n",
    "            \n",
    "            for i in range(start_index, len(s)):\n",
    "                if isPalindrome(start_index, i) == 1:\n",
    "                    ans.append(s[start_index: i+1])\n",
    "                    backtracking(s, res, ans, i+1) # 不能重复切割\n",
    "                    ans.pop()\n",
    "                else: # 不是回文字串，不能往下递归遍历，而是接着往右执行for循环\n",
    "                    continue\n",
    "        \n",
    "        backtracking(s, res, ans, 0)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 方法：回溯法。\n",
    "class Solution:\n",
    "    def isPalindrome(self, s, start, end):\n",
    "        while start < end:\n",
    "            if s[start] != s[end]:\n",
    "                return False\n",
    "            start += 1\n",
    "            end -= 1\n",
    "        return True\n",
    "    # 参数substrings时一组所有子字符串都是回文的分割。\n",
    "    def helper(self, s, start, substrings, result):\n",
    "        if start == len(s):\n",
    "            result.append(substrings[:])\n",
    "            return\n",
    "        for i in range(start, len(s)):\n",
    "            if self.isPalindrome(s, start, i):\n",
    "                substrings.append(s[start:i+1])\n",
    "                self.helper(s, i+1, substrings, result)\n",
    "                substrings.pop()\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        result = list()\n",
    "        self.helper(s, 0, list(), result)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        def backtrack(state, start, res):\n",
    "            if start == len(s):\n",
    "                res.append(list(state))\n",
    "                return\n",
    "            # print(state)\n",
    "            for j in range(1, len(s) + 1 - start):\n",
    "                    \n",
    "                if s[start:start+j] == s[start:start+j][::-1]:\n",
    "                    state.append(s[start:start+j])\n",
    "                        \n",
    "                    backtrack(state, start+j, res)\n",
    "                    state.pop()\n",
    "\n",
    "                    \n",
    "        res = [ ]\n",
    "        backtrack([ ], 0, res)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def process(self, startidx):\n",
    "        if startidx == self.length:\n",
    "            #print(\"aaaa\")\n",
    "            self.result.append(self.tmp[:])\n",
    "            return\n",
    "        if startidx > self.length:\n",
    "            return\n",
    "\n",
    "        for i in range(startidx, self.length):\n",
    "            #print(self.s[startidx:i+1], reversed(self.s[startidx:i+1]))\n",
    "            st = self.s[startidx:i+1]\n",
    "            #print(st, st[::-1])\n",
    "            if st == st[::-1]:\n",
    "                self.tmp.append(st)\n",
    "                self.process(i+1)\n",
    "                self.tmp.pop()\n",
    "\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        self.result = []\n",
    "        self.tmp = []\n",
    "        self.s = s\n",
    "        self.length = len(s)\n",
    "\n",
    "        self.process(0)\n",
    "\n",
    "        return self.result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        if not s:\n",
    "            return s\n",
    "        def f(start,path,res,s):\n",
    "            if start==len(s):\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            for i in range(start,len(s)):\n",
    "                if s[start:i+1]==s[start:i+1][::-1]:\n",
    "                    path.append(s[start:i+1])\n",
    "                    f(i+1,path,res,s)\n",
    "                    path.pop()\n",
    "        start=0\n",
    "        path=[]\n",
    "        res=[]\n",
    "        f(start,path,res,s)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        def backtrace(s, path, result, start):\n",
    "            if len(s) == start:\n",
    "                result.append(path[:])\n",
    "                return\n",
    "\n",
    "            # start为分割点\n",
    "            for i in range(start, len(s)):\n",
    "                if s[start:i+1] == s[start:i+1][::-1]:\n",
    "                    path.append(s[start:i+1])\n",
    "                    backtrace(s, path, result, i+1)\n",
    "                    path.pop()\n",
    "\n",
    "\n",
    "        path = []\n",
    "        result = []\n",
    "        backtrace(s, path, result, 0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def process(self, startidx):\n",
    "        if startidx == self.length:\n",
    "            #print(\"aaaa\")\n",
    "            self.result.append(self.tmp[:])\n",
    "            return\n",
    "        if startidx > self.length:\n",
    "            return\n",
    "\n",
    "        for i in range(startidx, self.length):\n",
    "            #print(self.s[startidx:i+1], reversed(self.s[startidx:i+1]))\n",
    "            st = self.s[startidx:i+1]\n",
    "            #print(st, st[::-1])\n",
    "            if st == st[::-1]:\n",
    "                self.tmp.append(st)\n",
    "                self.process(i+1)\n",
    "                self.tmp.pop()\n",
    "\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        self.result = []\n",
    "        self.tmp = []\n",
    "        self.s = s\n",
    "        self.length = len(s)\n",
    "\n",
    "        self.process(0)\n",
    "\n",
    "        return self.result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        res = self.func2(s,[],[])\n",
    "        return res\n",
    "\n",
    "\n",
    "    def func1(self,s):\n",
    "        if not s:\n",
    "            return False\n",
    "        for i in range(len(s)//2):\n",
    "            if s[i] != s[len(s)-i-1]:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def func2(self,s,arr1,arr2):\n",
    "        if not s:\n",
    "            if arr1:\n",
    "                arr2.append(arr1)\n",
    "            return arr2\n",
    "        for i in range(len(s)):\n",
    "            if self.func1(s[:i+1]):\n",
    "                arr1.append(s[:i+1])\n",
    "                self.func2(s[i+1:],arr1[:],arr2)\n",
    "                arr1.pop()\n",
    "\n",
    "        return arr2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        result = []\n",
    "        temp = []\n",
    "        self.backtracking(s, 0, temp, result)\n",
    "        return result\n",
    "\n",
    "    def backtracking(self, s, start, temp, result):\n",
    "        if start == len(s):\n",
    "            result.append(temp[:])\n",
    "            return \n",
    "        else:\n",
    "            for i in range(start, len(s)):\n",
    "                if self.ishuiwen(s, start, i):\n",
    "                    temp.append(s[start:i+1])\n",
    "                    self.backtracking(s, i+1, temp, result)\n",
    "                    temp.pop()\n",
    "\n",
    "    def ishuiwen(self, s, start, end):\n",
    "        while start < end:\n",
    "            if s[start] != s[end]:\n",
    "                return False\n",
    "            start += 1\n",
    "            end -= 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        # 预处理字符串, s[i, j]是否是回文串\n",
    "        # 状态方程 f(i, j) = f(i + 1, j - 1) && (s[i] == s[j])\n",
    "        self.s = s\n",
    "        self.ans = []\n",
    "        # print(self.isValid(0, 5))\n",
    "        self.dfs(0, [])\n",
    "        return self.ans\n",
    "    \n",
    "    def isValid(self, i , j):\n",
    "        # print(i, j)\n",
    "        if i >= j:\n",
    "            return True\n",
    "        else:\n",
    "            return self.isValid(i+1, j-1) and self.s[i] == self.s[j]\n",
    "    \n",
    "    def dfs(self, start, pre):\n",
    "        # start 索引前的字符串已经被分成若干回文串，且放置在pre内\n",
    "        if start == len(self.s):\n",
    "            # print(\"append \", pre)\n",
    "            # 遍历完整个字符串，将结果存入ans内\n",
    "            self.ans.append(pre.copy())\n",
    "        else:\n",
    "            # 遍历所有从start开始可能的回文子串进行搜索回溯\n",
    "            for j in range(start, len(self.s)):\n",
    "                if self.isValid(start, j):\n",
    "                    pre.append(self.s[start: j + 1])\n",
    "                    # print(pre)\n",
    "                    self.dfs(j + 1, pre)\n",
    "                    pre.pop()\n",
    "            \n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    @staticmethod\n",
    "    def check(s, start, end):\n",
    "        i = start\n",
    "        j = end\n",
    "\n",
    "        while i<j:\n",
    "            if s[i] != s[j]:\n",
    "                return False\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        \n",
    "        return True\n",
    "\n",
    "    def partition(self, s):\n",
    "        if len(s) == 1:\n",
    "            return [[s]]\n",
    "        \n",
    "\n",
    "        ans = []\n",
    "        self.f(s, 0, [], ans)\n",
    "\n",
    "        return ans\n",
    "\n",
    "    '''\n",
    "    s[index....]，返回所有的回文分割方案\n",
    "    '''\n",
    "    @staticmethod\n",
    "    def f(s, index, path, ans):\n",
    "        if index == len(s):\n",
    "            ans.append(deepcopy(path))\n",
    "            return\n",
    "\n",
    "        # s1\n",
    "        path.append(s[index])\n",
    "        Solution.f(s, index+1, path, ans)\n",
    "        path.pop()\n",
    "\n",
    "        # s2\n",
    "        for l in range(2, len(s) - index + 1):\n",
    "            if Solution.check(s, index, index + l - 1):\n",
    "                path.append(s[index:index+l])\n",
    "                Solution.f(s, index+l, path, ans)\n",
    "                path.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        result = []\n",
    "        self.helper(s, 0, [], result)\n",
    "        return result\n",
    "    \n",
    "    def helper(self, str, index, sublist, result):\n",
    "        if index == len(str):\n",
    "            result.append(sublist.copy())\n",
    "        else:\n",
    "            j = index\n",
    "            while j < len(str):\n",
    "                tmp_s = str[index:j+1]\n",
    "                if self.is_huiwen(tmp_s):\n",
    "                    sublist.append(tmp_s)\n",
    "                    self.helper(str, j+1, sublist, result)\n",
    "                    sublist.pop()\n",
    "                j += 1\n",
    "    \n",
    "    def is_huiwen(self, s):\n",
    "        start = 0\n",
    "        end = len(s) - 1\n",
    "        while start < end:\n",
    "            if s[start] == s[end]:\n",
    "                start += 1\n",
    "                end -= 1\n",
    "            else:\n",
    "                return False\n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, s:str, start:int, end:int) -> bool:\n",
    "        while start <= end:\n",
    "            if s[start] != s[end]:\n",
    "                return False\n",
    "            start += 1\n",
    "            end -= 1\n",
    "        return True\n",
    "    \n",
    "    def backtrace(self, s:str, index:int, path:List[str], result:List[List[str]]) -> None:\n",
    "        if index == len(s):\n",
    "            result.append(copy.deepcopy(path))\n",
    "        else:\n",
    "            for j in range(index, len(s)):\n",
    "                if self.isPalindrome(s, index, j):\n",
    "                    path.append(s[index: j+1])\n",
    "                    self.backtrace(s, j + 1, path, result)\n",
    "                    path.pop()\n",
    "\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        result = []\n",
    "        path = []\n",
    "        self.backtrace(s, 0, path, result)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    @staticmethod\n",
    "    @lru_cache\n",
    "    def check(s, start, end):\n",
    "        i = start\n",
    "        j = end\n",
    "\n",
    "        while i<j:\n",
    "            if s[i] != s[j]:\n",
    "                return False\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        \n",
    "        return True\n",
    "\n",
    "    def partition(self, s):\n",
    "        if len(s) == 1:\n",
    "            return [[s]]\n",
    "        \n",
    "\n",
    "        ans = []\n",
    "        self.f(s, 0, [], ans)\n",
    "\n",
    "        return ans\n",
    "\n",
    "    '''\n",
    "    s[index....]，返回所有的回文分割方案\n",
    "    '''\n",
    "    @staticmethod\n",
    "    def f(s, index, path, ans):\n",
    "        if index == len(s):\n",
    "            ans.append(deepcopy(path))\n",
    "            return\n",
    "\n",
    "        # s1\n",
    "        path.append(s[index])\n",
    "        Solution.f(s, index+1, path, ans)\n",
    "        path.pop()\n",
    "\n",
    "        # s2\n",
    "        for l in range(2, len(s) - index + 1):\n",
    "            if Solution.check(s, index, index + l - 1):\n",
    "                path.append(s[index:index+l])\n",
    "                Solution.f(s, index+l, path, ans)\n",
    "                path.pop()\n",
    "    \n",
    "    '''返回s[l...r]是否是回文串'''\n",
    "    @staticmethod\n",
    "    @cache\n",
    "    def g(s, l, r):\n",
    "        if l >= r:\n",
    "            return True\n",
    "\n",
    "        return Solution.g(s, l+1, r-1) and s[l] == s[r]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        def dfs(s):\n",
    "            res = []\n",
    "            if len(s)==0:\n",
    "                return [[]]\n",
    "            if len(s)==1:\n",
    "                return [[s]]\n",
    "            for i in range(len(s)):\n",
    "                strr = s[:i+1]\n",
    "                if strr!=strr[::-1]:\n",
    "                    continue\n",
    "                else:\n",
    "                    temp = dfs(s[i+1:])\n",
    "                    for tmp in temp:\n",
    "                        res.append([strr]+tmp)\n",
    "            return res\n",
    "        return dfs(s)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        n = len(s)\n",
    "        record = [[True] * n for _ in range(n)]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                record[i][j] = record[i+1][j-1] & (s[i] == s[j])\n",
    "        \n",
    "        def dfs(s, begin):\n",
    "            if len(s) == begin:\n",
    "                return [[]]\n",
    "            if len(s) - 1 == begin:\n",
    "                return [[s[-1]]]\n",
    "            ret = []\n",
    "            for i in range(begin, len(s)): \n",
    "                if not record[begin][i]:\n",
    "                    continue\n",
    "                tmp_sub = [s[begin:i+1]]\n",
    "                # print(tmp_sub)\n",
    "                tmp_ret = dfs(s, i+1)\n",
    "                # print(tmp_ret)\n",
    "                for t in tmp_ret:\n",
    "                    ret.append(tmp_sub + t)\n",
    "            return ret\n",
    "        return dfs(s, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        n = len(s)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def check(i, j):\n",
    "            if i >= j:\n",
    "                return True\n",
    "            return s[i] == s[j] and check(i + 1, j - 1)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i=0):\n",
    "            if i == n:\n",
    "                return [[]]\n",
    "            res = []\n",
    "            for j in range(i, n):\n",
    "                if check(i, j):\n",
    "                    sij = s[i:j + 1]\n",
    "                    res += [[sij] + k for k in dfs(j + 1)]\n",
    "            return res\n",
    "\n",
    "        return dfs()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        ans = [[]]\n",
    "        for c in s:\n",
    "            for i in range(len(ans)):\n",
    "                a = ans[i]\n",
    "                # directly add c could be a possbile solution\n",
    "                a.append(c)\n",
    "                # fina whether c could compose other recursive string with a's elements\n",
    "                if len(a) >= 2 and len(a[-2]) == 1 and a[-2] == a[-1]:\n",
    "                    ans += [a[:-2] + [''.join(a[-2:])]]\n",
    "                if len(a) >= 3 and len(a[-3]) == 1 and a[-3] == a[-1]:\n",
    "                    ans += [a[:-3] + [''.join(a[-3:])]]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        n = len(s)\n",
    "        idx = [list() for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            l, r= i, i\n",
    "            while l >= 0 and r < n and s[l] == s[r]:\n",
    "                idx[l].append(r+1)\n",
    "                l -= 1\n",
    "                r += 1\n",
    "            l, r = i, i+1\n",
    "            while l >= 0 and r < n and s[l] == s[r]:\n",
    "                idx[l].append(r+1)\n",
    "                l -= 1\n",
    "                r += 1\n",
    "        q = deque()\n",
    "        q.append([[], 0])\n",
    "        ret = list()\n",
    "        while q:\n",
    "            arr, i = q.popleft()\n",
    "            if i == n:\n",
    "                ret.append(arr)\n",
    "            else:\n",
    "                for j in idx[i]:\n",
    "                    q.append([arr+[s[i:j]], j])\n",
    "        return ret\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        def backtrack(state, start, res):\n",
    "            if start == len(s):\n",
    "                res.append(list(state))\n",
    "                return\n",
    "            print(state)\n",
    "            for j in range(1, len(s) + 1 - start):\n",
    "                    \n",
    "                if s[start:start+j] == s[start:start+j][::-1]:\n",
    "                    state.append(s[start:start+j])\n",
    "                        \n",
    "                    backtrack(state, start+j, res)\n",
    "                    state.pop()\n",
    "\n",
    "                    \n",
    "        res = [ ]\n",
    "        backtrack([ ], 0, res)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        n, right = len(s), 0\n",
    "        results = []\n",
    "        if len(s) == 1:\n",
    "            return [[s]]\n",
    "        # if s == s[::-1]:\n",
    "        #     results.append([s])\n",
    "        for right in range(n):\n",
    "            first_pan = s[:right+1]\n",
    "            if first_pan == first_pan[::-1]:\n",
    "                if len(first_pan) == n:\n",
    "                    results.append([first_pan])\n",
    "                    break\n",
    "                new_s = s[right+1:]\n",
    "                tmp_res = self.partition(new_s)\n",
    "                #print(tmp_res)\n",
    "                for l in tmp_res:  # [\"o\",\"o\",\"g\",\"l\",\"e\"]\n",
    "                    results.append([first_pan] + l)\n",
    "        return results\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        def isPalindrome(s, start, end):\n",
    "            while(start < end):\n",
    "                if s[start] != s[end]:\n",
    "                    return False\n",
    "                start += 1\n",
    "                end -= 1\n",
    "            return True\n",
    "        def helper(s, start, substring, ret):\n",
    "            if start == len(s):\n",
    "                ret.append([] + substring)\n",
    "                return\n",
    "            for i in range(start, len(s)):\n",
    "                if isPalindrome(s, start, i):\n",
    "                    substring.append(s[start:i + 1])\n",
    "                    helper(s,i + 1,substring,ret)\n",
    "                    substring.pop()\n",
    "        ret = []\n",
    "        helper(s,0,[],ret)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        res = []\n",
    "        if len(s)==0:\n",
    "            return [[]]\n",
    "        if len(s) == 1:\n",
    "            return [[s]]\n",
    "        for i in range(1,len(s)+1):\n",
    "            left  = s[:i]\n",
    "            right = s[i:]\n",
    "            if left==left[::-1]:\n",
    "                right = self.partition(right)\n",
    "                for i in range(len(right)):\n",
    "                    res.append([left] + right[i])\n",
    "        return res\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        if s == '': return [[]]\n",
    "\n",
    "        ans = []\n",
    "        for idx in range(len(s)):\n",
    "            if s[:idx+1] == s[idx::-1]:\n",
    "                tmp = [s[:idx+1]]\n",
    "                res = self.partition(s[idx+1:])\n",
    "                res = [ tmp+i for i in res ]\n",
    "                ans.extend(res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    回溯+记忆化搜索\n",
    "\n",
    "    时间O(2**n*n)\n",
    "    空间O(n**2)\n",
    "    '''\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        @cache\n",
    "        def isParlindrome(i,j):\n",
    "            if i>=j:\n",
    "                return True\n",
    "            return isParlindrome(i+1,j-1) if (s[i]==s[j]) else False\n",
    "        # 回溯\n",
    "        def dfs(idx):\n",
    "            if idx == n:\n",
    "                ret.append(temp[:])\n",
    "            for j in range(idx,n):\n",
    "                if isParlindrome(idx,j):\n",
    "                    temp.append(s[idx:j+1])\n",
    "                    dfs(j+1)\n",
    "                    temp.pop()\n",
    "        n = len(s)\n",
    "        ret = []\n",
    "        temp = []\n",
    "        dfs(0)\n",
    "        isParlindrome.cache_clear()\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        n = len(s)\n",
    "        ans, res = [], []\n",
    "        dp = [[False] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = True\n",
    "        for i in range(n-1, -1, -1):  #有点区间DP的意思,dp[i][j]字符串i到j是否为回文串。\n",
    "            for j in range(i+1, n, 1):\n",
    "                dp[i][j] = True if s[i] == s[j] and (j-i <2 or dp[i+1][j-1]) else False\n",
    "            \n",
    "        def dfs(cur):\n",
    "            if cur == n:\n",
    "                ans.append(res[:]) # 浅复制，一层List完全复制\n",
    "                return \n",
    "            for i in range(0, n-cur):\n",
    "                if dp[cur][cur+i]:  \n",
    "                    res.append(s[cur:cur+i+1])\n",
    "                    dfs(cur+i+1)\n",
    "                    res.pop()\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        return self.partition_impl(s, [])\n",
    "\n",
    "    def partition_impl(self, s: str, parts: List[str]) -> List[List[str]]:\n",
    "        partitions = []\n",
    "        for i in range(len(s)):\n",
    "            if not self.is_palindromic(s[:i + 1]):\n",
    "                continue\n",
    "            if i == len(s) - 1:\n",
    "                partitions.append(parts + [s])\n",
    "            else:\n",
    "                partitions += self.partition_impl(\n",
    "                    s[i + 1:],\n",
    "                    parts + [s[:i + 1]],\n",
    "                )\n",
    "        return partitions\n",
    "\n",
    "    def is_palindromic(self, s: str) -> bool:\n",
    "        if len(s) == 1:\n",
    "            return True\n",
    "        left, right = 0, len(s) - 1\n",
    "        while right > left:\n",
    "            if s[left] != s[right]:\n",
    "                return False\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        n = len(s)\n",
    "        dp = [[True]*n for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]\n",
    "        \n",
    "        res = list()\n",
    "        ans = list()\n",
    "\n",
    "        def back_track(i: int):\n",
    "            if i == n:\n",
    "                res.append(ans[:])\n",
    "                return\n",
    "            \n",
    "            for j in range(i, n):\n",
    "                if dp[i][j]:\n",
    "                    ans.append(s[i : j + 1])\n",
    "                    back_track(j + 1)\n",
    "                    ans.pop()\n",
    "\n",
    "        back_track(0)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        n = len(s)\n",
    "        def dfs(l,r,path,k):\n",
    "            if r>=n:\n",
    "                res.append(path)\n",
    "                return \n",
    "            while r+k<=n:\n",
    "                if s[l:r+k]==s[l:r+k][::-1]:\n",
    "                    dfs(r+k,r+k,path+[s[l:r+k]],1)\n",
    "                k+=1\n",
    "        res = []\n",
    "        dfs(0,0,[],1)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        # get_comb给定字符串s，返回字符串中回文串的位置\n",
    "        #\n",
    "        def get_comb(s):\n",
    "            ans = []\n",
    "            n = len(s)\n",
    "            for i in range(n):\n",
    "                for j in range(i+2,n+1):\n",
    "                    if judge(s[i:j]):\n",
    "                        ans.append((i,j-1))\n",
    "            return ans\n",
    "\n",
    "        def judge(s):\n",
    "            return s == s[::-1]\n",
    "\n",
    "        def dfs(dic,comb):\n",
    "            target = 0\n",
    "            ans = []\n",
    "            for c in comb:\n",
    "                if not dic[c[-1]]:\n",
    "                    ans.append(c)\n",
    "                    continue\n",
    "                target = 1\n",
    "                for cc in dic[c[-1]]:\n",
    "                    ans.append(c + [cc])\n",
    "            if target == 0:\n",
    "                return ans\n",
    "            return dfs(dic,ans)\n",
    "\n",
    "\n",
    "        # print(combs)\n",
    "        # print(dic)\n",
    "        def get_areas(combs):\n",
    "            ans = []\n",
    "            for c in [[comb] for comb in combs]:\n",
    "                _tmp = dfs(dic,[c])\n",
    "                ans += _tmp\n",
    "                # print(ans)\n",
    "                for t in _tmp:\n",
    "                    # if len(set(list(t))) == 1:\n",
    "                    #     ans.append([[0,i] for i in range(1,len(t))])\n",
    "                    #     continue\n",
    "                    _len = len(t) - 1\n",
    "                    for i in range(2 ** _len-1):\n",
    "                        code = \"1\" + str(bin(i))[2:].zfill(_len)\n",
    "                        _comb = []\n",
    "                        for idx,_code in enumerate(code):\n",
    "                            if _code == \"1\":\n",
    "                                _comb.append(t[idx])\n",
    "                        if _comb not in ans:\n",
    "                            ans.append(_comb)\n",
    "                # print(ans)\n",
    "                # print(\"--\"*100)\n",
    "            return ans\n",
    "        def get_ans(ans):\n",
    "            res = [[ss for ss in s]]\n",
    "            for a in ans:\n",
    "                idx = 0\n",
    "                idx2 = 0\n",
    "                _res = []\n",
    "                while idx < len(s):\n",
    "                    if idx2 < len(a):\n",
    "                        cur_area = a[idx2]\n",
    "                    if idx2 < len(a) and cur_area[0] == idx:\n",
    "                        _res.append(s[cur_area[0]:cur_area[1]+1])\n",
    "                        idx = cur_area[1]+1\n",
    "                        idx2 += 1\n",
    "                    else:\n",
    "                        _res.append(s[idx])\n",
    "                        idx += 1\n",
    "                # print(a,_res)\n",
    "                if _res not in res:\n",
    "                    res.append(_res)\n",
    "            return res\n",
    "        print(\"原始字符串:\",s)\n",
    "        if len(s) == 1:\n",
    "            return [[s]]\n",
    "        if len(set(list(s))) == 1:\n",
    "            ans = []\n",
    "            tmp = self.partition(s[1:])\n",
    "            for t in tmp:\n",
    "                ans.append(t + [s[0]])\n",
    "                t[-1] += s[0]\n",
    "                ans.append(t)\n",
    "            return ans\n",
    "\n",
    "\n",
    "        combs = get_comb(s)\n",
    "        print(\"回文子串的位置:\",combs)\n",
    "        n = len(combs)\n",
    "        dic = {}\n",
    "        for idx1 in range(n):\n",
    "            dic[combs[idx1]] = []\n",
    "            for idx2 in range(idx1+1,n):\n",
    "                if combs[idx2][0] > combs[idx1][1]:\n",
    "                    dic[combs[idx1]].append(combs[idx2])\n",
    "        print(\"构造一个用来枚举的字典：\",dic)\n",
    "        ans = get_areas(combs)\n",
    "\n",
    "        print(\"可以得到一个用数字表示的答案：\",ans)\n",
    "        res = get_ans(ans)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        ans = list()\n",
    "        path = list()\n",
    "        n = len(s)\n",
    "\n",
    "        def dfs(pos: int):\n",
    "            if pos == n:\n",
    "                ans.append(path.copy())\n",
    "                return\n",
    "            for j in range(pos, n):\n",
    "                t = s[pos:j + 1]\n",
    "                if t == t[::-1]:\n",
    "                    path.append(t)\n",
    "                    dfs(j + 1)\n",
    "                    path.pop()\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        # 分割字符串 dfs \n",
    "        ans = [] \n",
    "        path = [] \n",
    "        n = len(s) \n",
    "        # 每个位置 选择分割或不分割 使得每个子串都是回文串 所以进行了 约束判断 剪枝操作 \n",
    "        def dfs(i) :\n",
    "            if i == n:\n",
    "                ans.append(path.copy())  \n",
    "                return\n",
    "            for j in range(i, n):\n",
    "                t = s[i:j+1] # j是分割的位置 \n",
    "                if t == t[::-1]:\n",
    "                    path.append(t) \n",
    "                    dfs(j+1) \n",
    "                    path.pop() \n",
    "                    # dfs(j+1) \n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        ret = []\n",
    "        path = []\n",
    "        n = len(s)\n",
    "        dp = [[True] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(i+1, n):\n",
    "                dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]\n",
    "\n",
    "        def dfs(start):\n",
    "            if start == n:\n",
    "                ret.append(path[:])\n",
    "                return \n",
    "            for i in range(start, n):\n",
    "                if dp[start][i]:\n",
    "                    path.append(s[start:i+1])\n",
    "                    dfs(i+1)\n",
    "                    path.pop()\n",
    "                                        \n",
    "        dfs(0)\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "\n",
    "class Solution:\n",
    "    @staticmethod\n",
    "    @cache\n",
    "    def check(s, start, end):\n",
    "        i = start\n",
    "        j = end\n",
    "\n",
    "        while i<j:\n",
    "            if s[i] != s[j]:\n",
    "                return False\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        \n",
    "        return True\n",
    "\n",
    "    def partition(self, s):\n",
    "        if len(s) == 1:\n",
    "            return [[s]]\n",
    "        \n",
    "\n",
    "        ans = []\n",
    "        self.f(s, 0, [], ans)\n",
    "\n",
    "        return ans\n",
    "\n",
    "    '''\n",
    "    s[index....]，返回所有的回文分割方案\n",
    "    '''\n",
    "    @staticmethod\n",
    "    def f(s, index, path, ans):\n",
    "        if index == len(s):\n",
    "            ans.append(deepcopy(path))\n",
    "            return\n",
    "\n",
    "        # s1\n",
    "        path.append(s[index])\n",
    "        Solution.f(s, index+1, path, ans)\n",
    "        path.pop()\n",
    "\n",
    "        # s2\n",
    "        for l in range(2, len(s) - index + 1):\n",
    "            if Solution.check(s, index, index + l - 1):\n",
    "                path.append(s[index:index+l])\n",
    "                Solution.f(s, index+l, path, ans)\n",
    "                path.pop()\n",
    "    \n",
    "    '''返回s[l...r]是否是回文串'''\n",
    "    @staticmethod\n",
    "    @cache\n",
    "    def g(s, l, r):\n",
    "        if l >= r:\n",
    "            return True\n",
    "\n",
    "        return Solution.g(s, l+1, r-1) and s[l] == s[r]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        n = len(s)\n",
    "        f = [[True] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                f[i][j] = (s[i] == s[j]) and f[i + 1][j - 1]\n",
    "\n",
    "        ret = list()\n",
    "        ans = list()\n",
    "\n",
    "        def dfs(i: int):\n",
    "            if i == n:\n",
    "                ret.append(ans[:])\n",
    "                return\n",
    "            \n",
    "            for j in range(i, n):\n",
    "                if f[i][j]:\n",
    "                    ans.append(s[i:j+1])\n",
    "                    dfs(j + 1)\n",
    "                    ans.pop()\n",
    "\n",
    "        dfs(0)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        n = len(s)\n",
    "        isPali = [[False]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            isPali[i][i] = True\n",
    "        \n",
    "        for l in range(2,n+1):\n",
    "            for i in range(n-l+1):\n",
    "                j = i+l-1\n",
    "                if l == 2:\n",
    "                    isPali[i][j] = s[i] == s[j]\n",
    "                else:\n",
    "                    isPali[i][j] = (s[i]==s[j] and isPali[i+1][j-1])\n",
    "        \n",
    "        def allParts(idx):\n",
    "            nonlocal n\n",
    "            if idx == n:\n",
    "                return [[]] \n",
    "            ret = []\n",
    "            for j in range(idx,n):\n",
    "                if isPali[idx][j]:\n",
    "                    pre = s[idx:j+1]\n",
    "                    r = allParts(j+1)\n",
    "                    ret += [[pre]+post for post in r]\n",
    "            \n",
    "            return ret\n",
    "        \n",
    "        return allParts(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        n=len(s)\n",
    "        res=[]\n",
    "        path=[]\n",
    "\n",
    "        def dfs(i):\n",
    "            if i==n:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "\n",
    "            for j in range(i,n):\n",
    "                sub=s[i:j+1]\n",
    "                if sub==sub[::-1]:\n",
    "                    path.append(sub)\n",
    "                    dfs(j+1)\n",
    "                    path.pop()\n",
    "\n",
    "        \n",
    "\n",
    "        dfs(0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        path = []\n",
    "        res = []\n",
    "        n = len(s)\n",
    "        def dfs(depth):\n",
    "            if depth == n:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            for i in range(depth, n):\n",
    "                tmp = s[depth: i+1]\n",
    "                if tmp == tmp[::-1]:\n",
    "                    path.append(tmp)\n",
    "                    dfs(i+1)\n",
    "                    path.pop()\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        res=[]\n",
    "        n=len(s)\n",
    "\n",
    "        @cache\n",
    "        def is_valid(i, j):\n",
    "            if i >= j:\n",
    "                return 1\n",
    "            if s[i] == s[j]:\n",
    "                return is_valid(i + 1, j - 1)\n",
    "            else:\n",
    "                return -1\n",
    "\n",
    "\n",
    "        def dfs(path,i):\n",
    "            if i==n:\n",
    "                res.append(path[:])\n",
    "                return \n",
    "\n",
    "            for j in range(i,n):\n",
    "                if is_valid(i,j)==1:\n",
    "                    path.append(s[i:j+1])\n",
    "                    dfs(path,j+1)\n",
    "                    path.pop()\n",
    "\n",
    "        dfs([],0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "\n",
    "        n = len(s)\n",
    "\n",
    "        result = []\n",
    "\n",
    "        def dfs(s, sub):\n",
    "            if not s:\n",
    "                result.append(sub)\n",
    "                return\n",
    "\n",
    "            for i in range(len(s)):\n",
    "                if s[:i+1] == s[:i+1][::-1]:\n",
    "                    dfs(s[i+1:], sub + [s[:i+1]])\n",
    "        \n",
    "        dfs(s, [])\n",
    "    \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        # @cache\n",
    "        def ish(t):\n",
    "            return t==t[::-1]\n",
    "        def dfs(i,tmp):\n",
    "            # print(i,tmp)\n",
    "            if i==l:\n",
    "                ans.append(tmp[::])\n",
    "                return\n",
    "            for j in range(i+1,l+1):\n",
    "                t=s[i:j]\n",
    "                if ish(t):\n",
    "                    tmp.append(t)\n",
    "                    dfs(j,tmp)\n",
    "                    tmp.pop()\n",
    "            return\n",
    "        l=len(s)\n",
    "        ans=[]\n",
    "        dfs(0,[])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "\n",
    "        if len(s) == 0:\n",
    "            return []\n",
    "        path = []\n",
    "        reslist = []\n",
    "        def ishuiwens(ss):\n",
    "            l, r = 0, len(ss) - 1\n",
    "            while l <= r:\n",
    "                if ss[l] == ss[r]:\n",
    "                    l += 1\n",
    "                    r -= 1\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        def backtracking(startindex):\n",
    "            if startindex >= len(s):\n",
    "                reslist.append(path[:])\n",
    "                return\n",
    "            for i in range(startindex, len(s)):\n",
    "                \n",
    "                if ishuiwens(s[startindex:i+1]): #注意字符串截取是左闭右开的\n",
    "                   path.append(s[startindex:i+1])\n",
    "                else:\n",
    "                    continue\n",
    "                backtracking(i + 1)\n",
    "                path.pop()\n",
    "            return\n",
    "        \n",
    "        backtracking(0)\n",
    "        return reslist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        n = len(s)\n",
    "        dp = [[True] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]\n",
    "        \n",
    "        ret = []\n",
    "        res = []\n",
    "\n",
    "        def dfs(i: int):\n",
    "            if i == n:\n",
    "                ret.append(res[:])\n",
    "                return\n",
    "            for j in range(i, n):\n",
    "                if dp[i][j]:\n",
    "                    res.append(s[i: j + 1])\n",
    "                    dfs(j + 1)\n",
    "                    res.pop()\n",
    "        \n",
    "        dfs(0)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        result=[]\n",
    "        def backtrakc(path,s):\n",
    "            if len(s)==0:\n",
    "                result.append(path[:])\n",
    "                return\n",
    "            for i in range(1,len(s)+1):\n",
    "                if s[:i]==s[:i][::-1]:\n",
    "                    path.append(s[:i])\n",
    "                    backtrakc(path,s[i:])\n",
    "                    path.pop()\n",
    "        backtrakc([],s)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        ans=[]\n",
    "        path=[]\n",
    "        n=len(s)\n",
    "        def dfs(i):\n",
    "            if i==n:\n",
    "                ans.append(path.copy())\n",
    "                return\n",
    "            for j in range(i,n):\n",
    "                t=s[i:j+1]\n",
    "                if t==t[::-1]:\n",
    "                    path.append(t)\n",
    "                    dfs(j+1)\n",
    "                    path.pop()\n",
    "\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        n = len(s)\n",
    "\n",
    "        ans = []\n",
    "        path = []\n",
    "\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                ans.append(path.copy())\n",
    "                return\n",
    "            \n",
    "            for j in range(i, n):\n",
    "                t = s[i:j+1]\n",
    "                if t == t[::-1]:\n",
    "                    path.append(t)\n",
    "                    dfs(j+1)\n",
    "                    path.pop()\n",
    "        dfs(0)\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        ans = []\n",
    "        n = len(s)\n",
    "        path = []\n",
    "        if n == 0:\n",
    "            return ans\n",
    "        def helper(start_index):\n",
    "            if start_index >= n:\n",
    "                ans.append(path[:])\n",
    "                return\n",
    "            for i in range(start_index, n):\n",
    "                t = s[start_index:i + 1]\n",
    "                if t != t[::-1]:\n",
    "                    continue\n",
    "                path.append(t)\n",
    "                helper(i + 1)\n",
    "                path.pop()\n",
    "\n",
    "        helper(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        n = len(s)\n",
    "        dp = [[True for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "        for i in range(2, n + 1):\n",
    "            for j in range(n - i + 1):\n",
    "                dp[j][j + i - 1] = dp[j + 1][j + i - 2] and s[j] == s[j + i - 1]\n",
    "\n",
    "        self.cur = []\n",
    "        self.ans = []\n",
    "\n",
    "        def dfs(pos):\n",
    "            if pos == n:\n",
    "                self.ans.append(self.cur.copy())\n",
    "                return\n",
    "            \n",
    "            for i in range(pos + 1, n + 1):\n",
    "                if dp[pos][i - 1]:\n",
    "                    self.cur.append(s[pos:i])\n",
    "                    dfs(i)\n",
    "                    self.cur.pop()\n",
    "        \n",
    "        dfs(0)\n",
    "        return self.ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "\n",
    "        res = []\n",
    "        n = len(s)\n",
    "        temp = []\n",
    "\n",
    "        def valid(a):\n",
    "            n = len(a)\n",
    "            if n == 1: return True\n",
    "            i, j = 0, len(a) - 1\n",
    "            while i <= j and a[i] == a[j]:\n",
    "                i +=1\n",
    "                j -= 1\n",
    "            return j < i\n",
    "\n",
    "        def trackback(idx):\n",
    "\n",
    "            if idx == n:\n",
    "                res.append(temp.copy())\n",
    "                return\n",
    "            for i in range(idx + 1, n + 1):\n",
    "                if not valid(s[idx: i]): continue\n",
    "                temp.append(s[idx : i])\n",
    "                trackback(i)\n",
    "                temp.pop()\n",
    "\n",
    "        trackback(0)\n",
    "\n",
    "        return res\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        def justify(string):\n",
    "            i = 0\n",
    "            j = len(string) - 1\n",
    "            while i < j:\n",
    "                if string[i] != string[j]:\n",
    "                    return False\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            return True\n",
    "        \n",
    "        result = []\n",
    "        cur = []\n",
    "\n",
    "        def travel(left, right):\n",
    "            if right == len(s) + 1:\n",
    "                if len(\"\".join(cur)) == len(s):\n",
    "                    result.append(cur.copy())\n",
    "                return\n",
    "            if justify(s[left:right]):\n",
    "                print(s[left:right])\n",
    "                cur.append(s[left:right])\n",
    "                travel(right, right + 1)\n",
    "                cur.pop()\n",
    "            travel(left, right + 1)\n",
    "        \n",
    "        travel(0,1)\n",
    "        return result\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        res = []\n",
    "        n = len(s)\n",
    "        def ifH(s):\n",
    "            if len(s) == 1:\n",
    "                return True \n",
    "            l = 0\n",
    "            r = len(s) - 1\n",
    "            while l <= r:\n",
    "                if s[l] != s[r]:\n",
    "                    return False\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            return True \n",
    "\n",
    "        def backtrace(p, path):\n",
    "            nonlocal res, n\n",
    "            if p >= len(s):\n",
    "                res.append(copy.deepcopy(path))\n",
    "                return \n",
    "            for i in range(p, n):\n",
    "                if ifH(s[p : i + 1]):\n",
    "                    path.append(s[p : i + 1])\n",
    "                    backtrace(i + 1, path)\n",
    "                    path.pop(-1)\n",
    "        backtrace(0, [])\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    #回溯\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        res = []\n",
    "        n = len(s)\n",
    "        def ifH(s):\n",
    "            if len(s) == 1:\n",
    "                return True \n",
    "            l = 0\n",
    "            r = len(s) - 1\n",
    "            while l <= r:\n",
    "                if s[l] != s[r]:\n",
    "                    return False\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            return True \n",
    "\n",
    "        def backtrace(p, path):\n",
    "            nonlocal res, n\n",
    "            if p >= len(s):\n",
    "                res.append(copy.deepcopy(path))\n",
    "                return \n",
    "            for i in range(p, n):\n",
    "                if ifH(s[p : i + 1]):\n",
    "                    path.append(s[p : i + 1])\n",
    "                    backtrace(i + 1, path)\n",
    "                    path.pop(-1)\n",
    "        backtrace(0, [])\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        ans = []\n",
    "        n = len(s)\n",
    "        path = []\n",
    "\n",
    "        def dfs(index):\n",
    "            if index == n:\n",
    "                ans.append(path[:])\n",
    "                return\n",
    "            for i in range(index, n):\n",
    "                t = s[index: i + 1]\n",
    "                if t != t[::-1]:\n",
    "                    continue\n",
    "                path.append(t)\n",
    "                dfs(i + 1)\n",
    "                path.pop()\n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        ans=[]\n",
    "        path=[]\n",
    "        def dfs(i):\n",
    "            if i==len(s):\n",
    "                ans.append(path.copy())\n",
    "                return\n",
    "            for j in range(i,len(s)):\n",
    "                if s[i:j+1]==s[i:j+1][::-1]:\n",
    "                    path.append(s[i:j+1])\n",
    "                    dfs(j+1)\n",
    "                    path.pop()\n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        n = len(s)\n",
    "\n",
    "        ret = list()\n",
    "        ans = list()\n",
    "\n",
    "        @cache\n",
    "        def isPalindrome(i: int, j: int) -> int:\n",
    "            if i >= j:\n",
    "                return 1\n",
    "            return isPalindrome(i + 1, j - 1) if s[i] == s[j] else -1\n",
    "\n",
    "        def dfs(i: int):\n",
    "            if i == n:\n",
    "                ret.append(ans[:])\n",
    "                return\n",
    "            \n",
    "            for j in range(i, n):\n",
    "                if isPalindrome(i, j) == 1:\n",
    "                    ans.append(s[i:j+1])\n",
    "                    dfs(j + 1)\n",
    "                    ans.pop()\n",
    "\n",
    "        dfs(0)\n",
    "        isPalindrome.cache_clear()\n",
    "        return ret\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        res  = []\n",
    "        path = []\n",
    "        n = len(s)\n",
    "        table = {}\n",
    "        def ispart(t):\n",
    "            left = 0\n",
    "            right = len(t)-1\n",
    "            while left<right:\n",
    "                if t[left]!=t[right]:\n",
    "                    return False\n",
    "                else:\n",
    "                    left += 1\n",
    "                    right -= 1\n",
    "            return True\n",
    "        def dfs(i):\n",
    "            if i==n:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            for j in range(i,n):\n",
    "                t = s[i:j+1]\n",
    "                if (i,j+1) not in table: \n",
    "                    table[(i,j+1)] = ispart(t)\n",
    "                if table[(i,j+1)]:\n",
    "                    path.append(t)\n",
    "                    dfs(j+1)\n",
    "                    path.pop()\n",
    "        dfs(0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        def judge(ss):\n",
    "            l, r = 0, len(ss) - 1\n",
    "            while l <= r:\n",
    "                if ss[l] == ss[r]:\n",
    "                    l += 1\n",
    "                    r -= 1\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        ans = []\n",
    "        path = []\n",
    "        def dfs(i, start):\n",
    "            if i == len(s):\n",
    "                ans.append(path[:])\n",
    "                return\n",
    "            if i < len(s) - 1:\n",
    "                dfs(i+1, start)\n",
    "            \n",
    "            t = s[start: i + 1]\n",
    "            if t == t[::-1]:\n",
    "                path.append(t)\n",
    "                dfs(i+1, i+1)\n",
    "                path.pop()\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        n = len(s)\n",
    "        dp = [[True] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = True\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(i+1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i+1][j-1]\n",
    "                elif s[i] != s[j]:\n",
    "                    dp[i][j] = False\n",
    "        res = list()\n",
    "        path = list()\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            for j in range(i, n):\n",
    "                if dp[i][j]:\n",
    "                    path.append(s[i:j+1])\n",
    "                    dfs(j+1)\n",
    "                    path.pop()\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        n=len(s)\n",
    "        f=[[False]*(n) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i,-1,-1):\n",
    "                if j==i:\n",
    "                    f[j][i]=True\n",
    "                elif j+1==i and s[j]==s[i]:\n",
    "                    f[j][i]=True\n",
    "                elif s[i]==s[j] and f[j+1][i-1]:\n",
    "                    f[j][i]=True\n",
    "        path=[]\n",
    "        ans=[]\n",
    "        def dfs(i):\n",
    "            if i==n:\n",
    "                ans.append(path.copy())\n",
    "            for j in range(i,n):\n",
    "                if f[i][j]==True:\n",
    "                    path.append(s[i:j+1])\n",
    "                    dfs(j+1)\n",
    "                    path.pop()\n",
    "        dfs(0)\n",
    "        return ans\n",
    "                \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        ans = []\n",
    "        n = len(s)\n",
    "        splitString = []\n",
    "        def dfs(pos):\n",
    "            if pos == n:\n",
    "                ans.append(splitString.copy())\n",
    "                return\n",
    "            \n",
    "            for i in range(pos, n):\n",
    "                t = s[pos:i + 1]\n",
    "                # 回文\n",
    "                if t == t[::-1]:\n",
    "                    splitString.append(t)\n",
    "                    dfs(i + 1)\n",
    "                    splitString.pop()\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        n = len(s)\n",
    "        f = [[True] * n for _ in range(n)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(i+1, n):\n",
    "                f[i][j] = (s[i] == s[j]) and f[i+1][j-1]\n",
    "        ret = list()\n",
    "        ans = list()\n",
    "        def dfs(i :int):\n",
    "            if i == n:\n",
    "                ret.append(ans[:])\n",
    "                return\n",
    "            for j in range(i,n):\n",
    "                if f[i][j]:\n",
    "                    ans.append(s[i:j+1])\n",
    "                    dfs(j+1)\n",
    "                    ans.pop()\n",
    "        \n",
    "        dfs(0)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "        ans = []\n",
    "        path = []\n",
    "        n = len(s)\n",
    "        if n == 0:\n",
    "            return []\n",
    "        def judge_str(word):\n",
    "            valid = True\n",
    "            i,j = 0, len(word)-1\n",
    "            while j>i:\n",
    "                if word[j] != word[i]:\n",
    "                    valid = False\n",
    "                    break\n",
    "                j-=1\n",
    "                i+=1\n",
    "            return valid\n",
    "\n",
    "        def dfs(i, word):\n",
    "            if i >= n-1:\n",
    "                if judge_str(word):\n",
    "                    path.append(word)\n",
    "                    ans.append(path.copy())\n",
    "                    path.pop()\n",
    "                return\n",
    "\n",
    "            dfs(i+1, word + s[i+1])\n",
    "            if judge_str(word):\n",
    "                path.append(word)\n",
    "                dfs(i+1, s[i+1])\n",
    "                path.pop()\n",
    "\n",
    "        \n",
    "        dfs(0, s[0])\n",
    "        return ans\n",
    "            \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
